package 链表.单链表;

/**
 * https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247492022&idx=1&sn=35f6cb8ab60794f8f52338fab3e5cda5&scene=21#wechat_redirect
 */
public class _142_环形链表II {

    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (slow == fast) break;
        }

        // 这边说明没有环，因为fast已经遍历到最后了
        if (fast == null || fast.next == null) {
            return null;
        }

        // 从头开始，走k-m，就是环的起点
        slow = head;

        while (slow != head) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }
}
